이진 검색 트리로 균형을 이루도록 고안된 검색 트리 구조 중 하나이다.

(높이를 최소한으로 하기에 O(lgn)시간에 수행하도록 보장함)

각 노드당 한 비트의 추가 기억 공간을 가진다. (Red or Black)

노드의 색깔을 제한함으로서 경로가 다른 것보다 두 배 이상 길지 않음을 보장한다.(근사적 균형을 이룬 트리)

- color

- key

- left, right, p

...

1. 모든 노드는 적색이거나 흑색이다.

2. 루트는 흑색이다.

3. 모든 리프(nullptr)는 흑색이다.

4. 노드가 적색이면 그노드의 자식은 모두 흑색이다.

5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

레드블랙 트리는 리프를 하나의 경계노드(sentinel)을 사용해서 표현함

(하나의 경계 노드 T.nullptr을 생성하고 모든 리프와 루트의 부모를 표현하도록 함,

경계 노드의 필드 p, left, right, key 등이 프로시저 수행과정에서 채워질 수 있으나 이는 의미를 가지지 않음)

한 노드 x에서 리프까지의 경로에 있는 모든 흑색 노드의 개수; bh(x) -> 레드블랙 트리는 최대 2lg(n+1)의 높이를 가짐

Insert, Delete 연산은 레드블랙 특성을 위반할 수 있다.

따라서 특성을 복구해주기 위해서 일부 노드의 색깔과 포인터를 변경해 주어야 한다.

- LeftRotation

- RightRotation